操作系统 - 进程与CPU调度

本篇是操作系统课程笔记的第一篇，对应《操作系统导论》中进程、进程 API、受限直接执行与 CPU 调度等主题。

期中导引： 建议先通读 期中学习导航与主线，再配合 期中复习与典型题。复习题紧扣“60 分简答论述 + 40 分代码分析”考核标准，系统推演 fork 进程树、exec 映像覆盖、wait 退出状态回收、短路表达式求值、共享文件偏移量与 stdio 用户态缓冲区继承机制。

⭐ 本章考试重点：进程的步骤、进程状态的转换、fork() 函数的具体过程。对应下文 §1.1、§1.2 和 §2.1—2.3。

一、程序与进程

程序是静态的指令与数据；进程（process） 是程序的一次运行实例。可以简明类比：程序如静态菜谱，进程是依谱烹饪的动态执行过程；同一份菜谱可同时对应多个互不干扰的独立进程。

操作系统需要记录进程的地址空间信息、寄存器状态、打开文件、标识符及调度状态等。教材常以进程控制块（PCB）概括这类元数据；实际内核的数据结构和拆分方式各异。

1.1 从程序到进程：创建与执行的步骤 ⭐

⭐ 考试考点：进程的步骤。 先掌握程序如何被准备为一个可执行的进程，再与后面的 fork() 创建路径区分。

从操作系统的职责看，启动一个新程序需要完成以下工作；这是教学上的逻辑顺序，不要求所有内核逐项按此顺序实现。

1. 建立管理信息：分配进程标识（PID）及内核数据结构（PCB），记录父子关系、安全凭证与调度优先级。
2. 建立地址空间：为程序代码段、全局静态数据段等建立虚拟内存映射。装载并不要求立刻把整个可执行文件全部读入物理内存，实际支持按需调页（Demand Paging）。
3. 准备运行环境：设置用户栈（放置参数 argv 和环境变量 envp），准备动态堆分配所需的起始空间，并关联标准输入输出等文件引用。
4. 设置初始执行上下文：初始化程序计数器（PC，通常先指向语言运行时启动入口，再调用 main()）、栈指针（SP）等寄存器，使其具备执行条件。
5. 进入就绪并等待调度：准备完成不等于立即运行；调度器选中后，CPU 才真正开始执行该进程。

记忆线索：建记录 → 建空间 → 备环境 → 设上下文 → 等调度。

在 Unix 的 fork()＋exec() 路径中，这些职责分布在不同操作中：fork() 创建子进程并继承已有环境，exec() 将调用进程的程序映像替换为新程序。不要把上面的概念步骤误记为“fork() 每次都从磁盘重新装入程序”。

1.2 三种基本状态与转换 ⭐

⭐ 考试考点：进程状态的转换。 重点关注各状态之间的转换条件与不可逾越的边界。

• 就绪（ready）：具备执行条件，正在等待 CPU。
• 运行（running）：正在 CPU 上执行指令。
• 阻塞（blocked）：因等待 I/O 或同步事件而挂起，即使分配 CPU 也无法推进。

基本三态模型中没有“就绪 → 阻塞”：就绪任务未占用 CPU 执行指令，不可能自行发起阻塞操作。同样也不画“阻塞 → 运行”直接边：唤醒后逻辑上必须先进入就绪队列，经由调度器裁决后才获得 CPU。

例子：A 正在运行并请求一次需要等待的磁盘读取，于是 A：运行→阻塞；调度器选择 B，于是 B：就绪→运行。磁盘读取完成时，A：阻塞→就绪。此时 B 可以继续运行，直到调度规则决定切换。

1.3 PCB 与上下文：系统记住了什么

什么是上下文？两层上下文保存在哪里？

上下文（Context） 是某一时刻 CPU 所有内部寄存器的状态快照（包括程序计数器 PC、栈指针 SP、通用寄存器及状态标志寄存器 Flags）。物理 CPU 只有一套寄存器，暂停进程前必须把这些值保存下来，以便恢复时原地继续运行。

操作系统中实际上存在两层不同的上下文：

1. 用户态上下文（Trap Frame / 陷阱帧）：存放在当前进程的内核栈顶端。只要发生系统调用、中断或异常（由用户态进入内核态），硬件与中断入口汇编就会将用户态寄存器压入内核栈，用于退出内核时恢复用户现场。
2. 内核态调度上下文（Kernel Context）：存放在该进程的 PCB（或 thread_struct） 中。仅在调度器决定执行进程切换（如调用 switch_to）时，由内核保存当前执行流的内核栈指针与被调用者保存寄存器，用于在不同进程间轮换。

二、进程 API：创建与执行分离

⭐ 考试考点：fork() 函数的具体过程。 重点关注父子进程的返回值、执行位置，以及资源的复制与共享。

以 Unix 风格接口为例：

为什么 Unix 将创建与执行拆分为 fork() 和 exec() 两步？（OSTEP 核心设计哲学）
这种解耦在“子进程创建后”与“执行新程序前”留出了一段宝贵的操作窗口。最典型的受益者是 Shell：
在终端执行 wc -l < input.txt > output.txt 时，Shell 先 fork() 出子进程，在子进程中从容地关闭标准输入输出并重定向到目标文件（通过 open / dup2），随后才调用 exec("wc")。目标程序无需了解任何重定向逻辑，直接向标准输出写入即可，极大提高了系统的模块化与可组合性。

2.1 fork 的具体过程 ⭐

⭐ 考试考点：调用前只有父进程；成功后有父、子两个执行流，都从 fork() 返回处继续。子进程绝不会重新从 main() 开始！

调用 fork() 后，内核为子进程复制一份与父进程近乎完全相同的上下文与执行状态。由于程序计数器（PC）也被复制，子进程不会重新从 main() 执行，而是与父进程一样，从 fork() 系统调用的返回处继续往下跑。

内核通过返回值区分两者的身份：

• 对子进程：返回 0；
• 对父进程：返回刚创建的子进程 PID；
• 发生错误（如系统进程数超限或内存耗尽）：返回 -1，不创建子进程。

从调用者角度，可以把创建过程理解为：

这是接口行为的概念模型。返回值不是当前进程自己的 PID；当前 PID 用 getpid() 查询。接口语义核对：Linux fork(2)。

2.2 fork 后到底共享什么

父子进程拥有各自独立的虚拟地址空间语义，普通变量后续的修改互不可见。

• 私有变量与写时复制（COW）：若每次 fork() 都物理复制全部内存，开销极大且通常无意义（子进程往往紧接着调用 exec()）。现代系统采用写时复制（Copy-on-Write）：创建时父子共享物理只读页，仅当某一方尝试写入修改时，硬件触发写保护缺页异常，内核才为此页分配并复制私有物理副本。既保证了逻辑隔离，又兼顾了创建性能。
• 文件描述符与文件偏移量：父子各自的描述符表是独立的，但继承的表项指向同一个内核打开文件描述（Open File Description）。因此，父子进程共享文件读取/写入偏移量（File Offset）。父进程读取若干字节后，子进程接着读取会从新的偏移量继续。

2.3 一段可运行的 fork 示例

以下示例适用于支持 POSIX 进程接口的环境，并假设调用者是单线程程序。重点观察：执行从哪里继续、x 是否共享，以及 waitpid() 对输出顺序的影响。

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void) {
    int x = 10;
    pid_t pid = fork();

    if (pid < 0) {
        perror("fork");
        return EXIT_FAILURE;
    }
    if (pid == 0) {
        x = 20; // 子进程修改私有副本，不会影响父进程的 x
        printf("child: x=%d\n", x);
        return EXIT_SUCCESS;
    }

    int status;
    // 父进程主动等待子进程收工
    while (waitpid(pid, &status, 0) == -1) {
        if (errno == EINTR) continue;
        perror("waitpid");
        return EXIT_FAILURE;
    }
    printf("parent: x=%d\n", x); // 输出仍为 10
    return WIFEXITED(status) ? WEXITSTATUS(status) : EXIT_FAILURE;
}

保存为 fork_demo.c，编译运行：

cc -std=c11 -Wall -Wextra fork_demo.c -o fork_demo
./fork_demo

正常运行时输出：

child: x=20
parent: x=10

子进程修改的是自己的 x。父进程的输出位于等待之后，所以本例中子进程先完成输出；这不是 fork() 自动保证子进程先运行。去掉等待关系后，就不能依赖这样的顺序。

2.4 输出顺序与缓冲的两个问题

fork() 成功后，父子进程谁先运行通常没有保证。若 fork() 之前有尚未刷出的标准 I/O 缓冲，缓冲内容会被一同复制到子进程中；后续双方退出刷新时可能出现重复输出。关键在于复制了未刷新的用户态缓冲区，并非子进程回头重新执行了前面的 printf()。分析题目时，可在 fork() 前调用 fflush() 排除干扰。

进程数量题也要沿控制流计算：连续执行 $n$ 次无条件 fork()，只有在每个现存进程都执行每一次调用、调用全部成功且中途不退出时，总数才为 $2^n$，新增数为 $2^n-1$。遇到分支、短路运算和 exec() 时，应画进程树逐条判断。

2.5 exec、wait 与退出：把生命周期接起来

• exec()：成功后替换原程序映像，建立新程序所需的地址空间并转到新入口，PID 保持不变。这里的“替换”不要求逐字节物理覆盖原内存，也不要求一次性把新程序全部读入内存。Linux execve(2)。
• 僵尸进程（Zombie）：子进程已终止退出，内核已释放其大部分内存资源，但仍保留其 PID、退出状态及 CPU 用时统计等元数据，等待父进程调用 wait() / waitpid() 读取并释放。若父进程迟迟不回收，僵尸进程将持续占用系统的 PID 资源。
• 孤儿进程（Orphan）：原父进程先退出，存活的子进程成为孤儿。在 Linux 上它会被最近的子收割者（subreaper）或 1 号进程（init / systemd）接管。接管者会在其退出时负责回收。

教材 §4.5（书内第 25 页）把僵尸作为“已退出但尚未清理”的最终状态介绍：保留这段状态，是为了让父进程知道子进程是否成功完成。

孤儿不是三态模型之外的一种调度状态。 它描述的是父子关系；僵尸描述的是退出后的生命周期阶段。二者不应与“运行、就绪、阻塞”并排当成同一分类。

短暂的僵尸阶段通常是正常现象，长期大量积累才说明回收机制有问题。对僵尸发送 kill -9 不能代替回收：它已经没有可终止的执行流，需要处理的是父进程的回收逻辑。显式设置 SIGCHLD 为 SIG_IGN 或使用 SA_NOCLDWAIT 等配置还可改变退出状态的保留行为，因此“子进程退出后一定留下僵尸”也不准确。Linux wait(2)。

实际 Shell 对内建命令、管道和后台任务另有处理；上述过程用于说明一个外部命令的基本生命周期。

2.6 与计算机系统课程串起来：退出、信号与回收

之前的《计算机系统 - 程序执行》第七节已经讲过：fork → execve → 动态链接 → _start → main → exit → waitpid。操作系统这里补上的重点是最后两步：程序停止执行，与内核清理其退出记录，是两件事。

在《CSAPP - Shell Lab》的 waitfg && sigchld_handler 部分，之前遇到过：子进程结束了，Shell 却一直认为前台任务还在。这里需要区分三层工作：

1. SIGCHLD 是通知：告诉 Shell 子进程发生了状态变化；收到信号本身不等于已完成回收，而且通知也可能对应停止等事件。
2. waitpid() 读取状态：对已经终止的子进程完成回收；若报告的是停止状态，该进程还活着，不能当成退出处理。
3. deletejob() 更新 Shell 自己的任务表：这张用户态表不是内核进程表。只删任务记录不能回收僵尸；只回收却不更新任务表，也可能让 waitfg 继续误判。

Shell Lab 用 while (waitpid(-1, &status, WNOHANG | WUNTRACED) > 0) 循环处理可取得的子进程状态，因为普通 SIGCHLD 信号可能合并，一次通知不一定只对应一个子进程事件。WNOHANG 让当前没有可报告状态时立即返回，避免处理函数一直等；具体终止、停止等情况再通过 WIFEXITED、WIFSIGNALED、WIFSTOPPED 分别判断。

关联自测：后台命令结束后，Shell 还能接收输入，是否说明没有僵尸？——不能。交互正常和回收正确是两回事；后台任务也需要回收，只是不必让主交互流程一直阻塞等待它。

2.7 在 Linux 里观察这些概念

学到进程时，可以直接用下面的命令观察，不必先写实验程序：

# 查看进程身份、父进程、状态和命令行
ps -eo pid,ppid,stat,comm,args

# 当前 Shell 的 PID 是 $$；观察它由谁启动
echo $$
ps -p "$$" -o pid,ppid,stat,args

# 查看进程树及 PID（需安装提供 pstree 的 psmisc 工具包）
pstree -p

# 动态观察 CPU 使用情况
top

PID 是进程号，PPID 是当前父进程号。STAT 的第一个字母表示主要状态，后面的字符提供附加信息，例如 + 表示属于终端的前台进程组。

Linux 的状态码比教材三态模型更细。 特别是 R 同时包含运行与就绪；孤儿进程没有专门的“孤儿状态字母”，需要结合父子关系变化判断，单看 PPID=1 也不能还原它的全部生命周期。

在交互式 Shell 中，jobs -l 查看的是当前 Shell 管理的作业，ps 查看的是系统进程；一个管道作业还可能包含多个进程。Ctrl-Z 停止前台作业，bg 让停止的作业在后台继续，fg 将作业带回前台——这正好对应 Shell Lab 中的 SIGTSTP、SIGCONT 和前后台任务管理。

另一个易混点：Shell 的 wait 是内建命令，用来等待它管理的子进程或作业；C 程序中的 wait() / waitpid() 是进程等待接口。它们有关联，但不是同一个使用层次，Shell 也不能靠 wait 任意回收其他进程的子进程。

观察题：sleep 通常显示 S 而不是 Z，为什么？——它仍活着，只是在等待计时完成；僵尸则已经结束执行，只剩待回收记录。

2.8 本机实录：亲眼看到父子进程与等待状态

下面的输出采集于 2026-09-20 的 macOS／Darwin arm64 环境，是实际运行结果。它同属 Unix 环境，但工具参数、调度实现和部分状态显示与 Linux 不完全相同；不要把 macOS 输出当成 Linux 截图。

用一个四秒后自动结束的 sleep，观察父子关系：

/bin/zsh -f -c 'sleep 4 & demo_pid=$!; ps -p $$,$demo_pid -o pid,ppid,stat,ni,comm; wait $demo_pid'

实际输出：

  PID  PPID STAT NI COMM
94990 80124 Ss    0 /bin/zsh
94991 94990 SN    5 sleep

• 看关系：sleep 的 PID 是 94991，PPID 是 94990，正好对应上面那一行 Shell 的 PID。这就是父子关系在进程表中的表现；PID 每次运行都可能不同。
• 看状态：两行的首字母都是 S，表示采样时处于睡眠。sleep 在等待时间到达，Shell 此时也在等待前台的 ps 命令完成；输出结束后才执行后面的 wait，等待后台 sleep 结束。
• 看附加标记：按本机 man ps，小写 s 表示会话首进程，N 表示降低了 CPU 调度优先级。它们不是另外两种独立的主状态。
• 看 NI：本次 Shell 为 0，后台 sleep 为 5。这与 zsh 默认开启的 BG_NICE 行为相符：后台作业以较低优先级运行。不能因此推出“所有 Shell 中加 & 都必然让 NI 变成 5”。本机 man zshoptions 可查该选项。

$$ 是当前 Shell 的 PID，$! 是最近一个后台任务的 PID，& 表示让命令在后台执行。最后的 wait 使 Shell 等待并取得这个子进程的结束状态，整个例子会自行结束。

2.9 本机 top：为什么 sleeping 也有 CPU 使用率

macOS 的 top 可以用日志模式采样两次，间隔一秒，并只显示指定字段：

top -l 2 -s 1 -n 5 -o cpu -stats pid,command,cpu,mem,threads,state

下面节选第二次采样的概况和两行进程数据，其余输出省略。选择第二次，是因为本机 man top 明确说明，首次采样的进程 %CPU 缺少前一次采样作为有效计算基准。

Processes: 704 total, 4 running, 700 sleeping, 5423 threads
Load Avg: 8.03, 4.66, 4.22
CPU usage: 23.45% user, 12.47% sys, 64.7% idle
PID    COMMAND          %CPU MEM    #TH    STATE

608    WindowServer     42.8 1224M- 24     sleeping

0      kernel_task      19.6 67M-   714/10 running

先看整机：这次采样中，进程总数为 704，线程总数为 5423，二者不是同一个数量；CPU 概况把时间分为用户态、内核态和空闲部分。

再看单个进程：WindowServer 的状态是 sleeping，但 %CPU 为 42.8，并不矛盾。状态表示采样时观察到的状态，CPU 使用率反映前后两次采样之间消耗的 CPU 时间；它完全可能先运行了一段时间，再进入等待。多线程进程的汇总信息还涉及多个线程，不能把它简单当成一条永不变动的状态线。

本机的 MEM 表示进程的物理内存占用指标（physical memory footprint），不是 Linux VIRT，也不能不加区分地当成 Linux RES。末尾的 - 表示相较上次采样减少，+ 则表示增加。#TH 是线程数，斜线后若显示数字，则是运行中的线程数：这里 714/10 表示总计 714 个线程，其中 10 个被报告为运行中。

2.10 Linux top 字段速查：PID、PR、NI 到底是什么

Linux 上常见的是 procps-ng 的 top，典型表头如下。这里只列字段，未将本机 macOS 数据伪装为 Linux 输出。 字段顺序、单位及可见列都可以配置。

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND

常用交互键：P 按 CPU 排序，M 按内存排序，1 切换各逻辑 CPU 的显示，H 切换线程视图，q 退出。字段与按键参考：procps-ng top(1)。

PR 与 NI：优先级和“谦让程度”

对 Linux 常规 nice 调节机制而言，NI 越小，通常获得越高的调度权重：-20 最不谦让，19 最谦让，0 是常见默认值。它影响有竞争时的 CPU 分配，不是固定百分比配额，也不是“每次必须先运行”的保证；睡眠或等待 I/O 的任务不会因为 NI 更小就立即获得所需事件。Linux nice(2)。

普通非实时任务常见的 top 显示关系是 PR = 20 + NI：

这里的数字越小通常表示优先级越高。不要将此关系套到实时任务或 macOS 的优先级字段上。 Linux 实时调度有独立的优先级与策略，top 可能显示 rt 等形式；调度策略、CPU 亲和性和资源分组等条件也会影响实际运行结果。内核导出的 priority／nice 定义。

顶部概况：负载不等于 CPU 百分比

Linux 的 load average 三个值对应最近 1、5、15 分钟的平均负载，统计可运行任务以及不可中断等待任务。它不是百分数，也不只是“有多少进程正在 CPU 上执行”；判断是否拥挤需要结合可用逻辑 CPU 数和等待原因。例如负载较高、CPU 却不忙，可能与不可中断 I/O 等待有关，不能只凭一个数字下结论。Linux uptime(1)。

读资源表时，可以沿着三条线思考：PR／NI 联系调度策略，S 联系状态转换，VIRT／RES 联系虚拟内存。同一个 top 界面其实把后面几章的知识放到了一起。

三、受限直接执行（Limited Direct Execution）与上下文切换

CPU 虚拟化面临着操作系统的核心挑战：如何在让程序获得原生执行性能的同时，保持操作系统的安全性与绝对控制权？

3.1 什么是受限直接执行（LDE）？

若由操作系统逐条解释模拟用户指令，安全性虽高但性能极低（开销可达数十倍）；若直接将程序置于裸机硬件上全速运行，操作系统又无法防范死循环或破坏性操作。

受限直接执行（LDE） 的折中方案是：

常规指令直接在物理 CPU 上全速执行（直接执行）；一旦涉及硬件资源或潜在破坏性操作，必须受控由内核接管，且死循环可被硬件强行打断（受限）。

3.2 限制一：阻止越权——用户态与内核态的关系

用户态与内核态的划分并非两个独立进程，而是 CPU 硬件层面的特权级分离（如 x86 的 Ring 3 与 Ring 0，ARM 的 EL0 与 EL1）：

1. 指令分级：

   • 特权指令：只能在内核态执行。包括开关硬件中断（cli/sti）、直接读写 I/O 端口、修改页表基址寄存器（如 CR3）、停机（hlt）等。用户态尝试执行会触发硬件异常，由内核终止该进程。
   • 非特权指令：用户态和内核态皆可执行。包括通用寄存器算术运算、用户栈操作、函数跳转等，完全由硬件直接执行。

2. 跨越边界的三道闸门与中断向量表（IVT）：
   用户程序无法自行提升特权级，只能通过以下硬件机制进入内核态：

   • 系统调用（Trap）：同步触发。程序主动请求内核服务（如 read()、fork()）。
   • 异常 / 故障（Fault）：同步触发。当前指令发生错误（如除以零、段错误、缺页异常）。
   • 硬件外部中断（Interrupt）：异步触发。外设引脚发出的电信号（如时钟中断、网络包到达）。

   中断向量表与上下文保存的软硬件协同：

   核心本质：中断向量表（IVT）负责“寻址路由”（解决跳去哪），内核栈上的上下文压栈负责“现场保护”（解决怎么恢复）。

   触发事件系统调用、异常或外部中断，请求进入受控的内核入口。

   ↓

   入口定位 · 去哪里通过体系结构规定的入口机制找到处理程序；中断与异常可通过向量表定位。

   现场保存 · 怎么回来硬件与入口汇编协作，保存恢复执行所需的寄存器状态。

   ↓

   执行内核处理程序处理完成后，沿对应返回路径恢复现场。

   这是概念流程。x86 的中断／异常使用 IDT；现代 syscall 指令的入口机制不同，不是所有进入内核的路径都查询同一张表。

   软硬件协同执行时序（以系统调用/中断为例）：

   1. 用户态：发起请求或被事件打断程序执行触发系统调用／异常，或 CPU 收到外部中断。
   2. 硬件：转入受控入口按体系结构规则改变执行模式、定位入口并保存必要状态。
   3. 入口汇编：补全现场建立内核执行环境，保存软件负责的寄存器，组织陷阱帧等状态。
   4. 内核：执行服务处理读取、缺页或设备事件；需要等待时也可能触发调度。
   5. 返回路径：恢复用户态执行恢复现场，通过对应返回机制继续用户程序。

   此图假设最终返回同一执行流。硬件自动保存哪些寄存器、何时切栈、使用哪条返回指令，取决于体系结构与入口类型。

   • 查表与硬件自动压栈：CPU 根据向量号查中断向量表获取入口地址；同时，硬件自动切换至该进程的内核栈，并在跳转前自动将核心寄存器（PC、SP、Flags、CS 等）压入内核栈；
   • 软件压栈构建 Trap Frame：跳转到中断向量表指向的处理程序入口后，第一段汇编代码将剩余的通用寄存器（RAX、RBX 等）全部压入内核栈，形成完整的用户态上下文（Trap Frame / pt_regs）；
   • 内核处理与恢复现场：内核完成业务逻辑后，汇编弹出通用寄存器，最后执行 iret / return-from-trap 指令，硬件自动从内核栈弹回核心寄存器并降权切回用户态，原程序无缝继续。

3. 为什么必须使用双栈模型（用户栈 vs 内核栈）？
   每个进程都配有一个私有的用户栈和一个小型的内核栈（通常 8KB/16KB）：

   • 安全性：用户栈位于用户空间，用户指针可随意读写。若特权级现场和内核函数调用帧压入用户栈，恶意代码可篡改返回地址直接劫持内核；
   • 健壮性：用户栈可能发生溢出或指针损坏。进入内核时切换到预设的专用内核栈，可避免在压栈保护现场时引发连续故障导致整机崩溃。

4. 虚拟地址空间与故障隔离：
   内核空间通常常驻于每个进程虚拟地址空间的高位（通过页表项 U/S 标志位进行硬件阻隔）。因此，系统调用发生时仅改变 CPU 特权模式，无需切换页表基址（CR3），也无需刷新 TLB 缓存。

   • 故障隔离：用户态程序崩溃仅导致该进程被终止（如抛出 SIGSEGV）；内核态代码若发生崩溃则意味着系统核心失控，只能触发 Kernel Panic 或蓝屏停机。

3.3 限制二：防止独占——操作系统如何夺回控制权？

哲学悖论：当一个用户进程正在 CPU 上全速运行时，意味着操作系统此时根本没有在运行。如果操作系统没有运行，它该如何采取行动制裁恶意代码、重新夺回 CPU？

面对这一难题，操作系统历史上存在两种设计哲学：

1. 协作方式（Cooperative: Wait For System Calls）——“全靠自觉”

• 运行机制：操作系统假定所有进程都会合理运行。长期占用 CPU 的进程被假定会定期主动发起系统调用（如读写磁盘），或显式调用 yield() 将 CPU 控制权归还给操作系统。
• 致命缺陷：若某程序存在 Bug 或恶意写出 while(1); 死循环，它既不发起系统调用也不报错。操作系统将永远无法夺回控制权！
• 历史代价：早期系统（如早期 Mac OS 与 Windows 3.1）均采用协作调度。一旦单个程序卡死，整机完全无响应，唯一的解决途径就是物理断电重启。

2. 非协作方式（Non-Cooperative: The OS Takes Control）——“硬件强行夺权”

现代操作系统彻底放弃了“信任程序”的假设，引入硬件外力——时钟中断（Timer Interrupt）：

• 开机布防：在系统引导阶段，操作系统向硬件时钟芯片发送特权指令，命令其每隔数毫秒（如 10ms）向 CPU 引脚发送一次硬件中断信号；
• 强制打断：无论当前程序在执行什么（哪怕是死循环），一旦时钟信号到达，CPU 硬件强行打断当前指令流水线；
• 重获统治：硬件自动将用户现场保存至内核栈，切换为内核态，并将 PC 强行指向内核的时钟中断处理程序。此时，操作系统重新掌控了 CPU！

3.4 进程上下文切换（Context Switch）：从 A 切换到 B

当操作系统通过时钟中断（或系统调用）重新拿回控制权后，内核的调度器（Scheduler）必须做出裁决：是让当前进程继续运行，还是换下一个进程运行？

若决定换人，内核将执行底层的上下文切换（Context Switch，通常是汇编函数 switch() 或 swtch()）。

软硬件协同切换全流程（时钟中断驱动）

很多初学者最大的困惑是：为什么在内核里执行一次从陷阱返回（iret），醒过来的会是进程 B 而不是进程 A？

答案全在 “切换内核栈指针” 这一步：

⭐ 考点辨析：两次不同性质的寄存器保存

在上述切换过程中，发生了两组完全不同性质的寄存器保存/恢复，切勿混淆：

3.5 上下文切换的耗时与系统开销

为什么操作系统教材（如 OSTEP）极其强调测量上下文切换的耗时？

上下文切换期间，CPU 完全没有运行任何用户代码（既没算数据也没刷页面）。这是操作系统为了实现分时复用（多任务假象）而不得不缴纳的纯粹管理税（Overhead Tax）。

上下文切换的开销由两部分组成：

1. 直接开销（Direct Cost）——微秒级

• 保存与恢复几十个 CPU 寄存器；
• 切换内核栈与执行调度算法选择下一个任务；
• 切换虚拟内存空间（重新装载页表基址寄存器，如 x86 的 CR3）。
• 实测耗时：通过微基准测试工具（如经典的 lmbench）测得，现代 CPU 上直接保存恢复现场仅需 亚微秒至数微秒（$\approx 1\sim 3\mu s$）。

2. 间接隐形成本（Indirect Cost）——最致命的性能杀手

比起写几个寄存器，真正昂贵的是让 CPU 缓存“变冷”（Cold Cache / 缓存污染）：

• 热缓存（Hot Cache）：进程 A 运行时，CPU 的 L1/L2 高速缓存以及 TLB（地址转换快表）装满了 A 的热点指令与数据，访存仅需数个纳秒。
• 缓存颠簸（Cache Thrashing）：切到进程 B 后，B 的数据会迅速冲刷覆盖原有的缓存；
• 冷启动惩罚：当再切回进程 A 时，A 面临大面积的 Cache Miss 和 TLB Miss，必须频繁停顿去慢速的物理内存（DRAM）中重新拉取数据，访存延迟骤增上百倍！

3. 权衡取舍：时间片（Time Slice）为什么不能太长也不能太短？

上下文切换的开销直接决定了 CPU 调度器的时间片设定：

               ┌─── 时间片太短 (如 1ms)  ────> 切换开销与缓存损耗占比过高 (>10%)，CPU 尽在打白工，系统吞吐量雪崩
时间片设计权衡 ─┤
               └─── 时间片太长 (如 1000ms) ──> 切换开销占比几乎为零，但交互极差，用户敲键盘点鼠标感到明显卡顿

• 黄金折中点：现代通用操作系统（Linux CFS、Windows）将默认时间片通常定在 10ms ～ 50ms。此时上下文切换耗时占总 CPU 时间比例 $< 1\%$，同时又能保证人类肉眼完全无法察觉的高刷新流畅度。

3.6 概念辨析：模式切换 vs 进程切换

四、什么是调度？（心智模型与两把量尺）

4.1 调度的本质：多任务的“排队分配学”

如果你的电脑只有一个 CPU 核心，但此时后台有浏览器、网易云音乐、IDE、微信等数十个进程都处于就绪状态（Ready），都在眼巴巴地抢着要运行。

调度（Scheduling）的本质：就像银行大厅的叫号经理或机场跑道的空中管制员。就绪队列里站着一堆排队待命的进程，调度器根据一套既定规则，决定 ** “下一个时间段，CPU 的宝贵算力赏给谁用？用多久？谁先跑、谁后跑、谁该滚去排队？” **

调度算法不是凭空冒出来的数学题，它是计算机科学家在面对一系列现实限制时，打怪升级、妥协折中的产物。

4.2 OSTEP 的 5 个“天真假设”

为了看清调度的本质，教材《操作系统导论》先设定了 5 个极度理想、近乎幼稚的工作负载假设（Workload Assumptions）：

1. 假设 1：每个作业（Job）的运行时间都一模一样长；
2. 假设 2：所有作业都在同一绝对时刻到达系统；
3. 假设 3：作业一旦启动，就运行至彻底结束，中途绝不被抢占（非抢占）；
4. 假设 4：所有作业只占用 CPU，不做任何磁盘读写或网络 I/O；
5. 假设 5：每个作业要跑多久，操作系统事先全都知道（上帝视角 / Oracle）。

💡 整章的核心故事线：现实中这 5 个假设全都是假的！ 调度算法的演进，本质上就是逐个打破这 5 个天真假设，在一次次翻车中逼出新算法的过程！

4.3 衡量调度好坏的两把尺子

调度算法怎么比出高下？不能靠玄学，操作系统定义了两把最核心的量尺：

1. 周转时间（Turnaround Time）——衡量“批处理干得快不快”

• 定义：从任务到达系统，到它彻底执行完成并退出所花费的总耗时。
  $T_{\text{turnaround}} = T_{\text{完成时刻}} - T_{\text{到达时刻}}$
• 生活比喻：寄快递或叫外卖。从你在手机上下单那一刻起，到外卖真正送到你手上的全部等待时长。这个指标侧重于系统的总吞吐量与批处理效率。

2. 响应时间（Response Time）——衡量“人机交互卡不卡”

• 定义：从任务到达系统，到它第一次获得 CPU 并开始运行的等待耗时。
  $T_{\text{response}} = T_{\text{首次运行时刻}} - T_{\text{到达时刻}}$
• 生活比喻：去餐厅点菜。从你点好单到服务员端上第一杯水或第一道小菜的时间。只要第一道菜上来了，你就知道厨房接单了，不会觉得被冷落。这个指标侧重于交互式体验（让用户敲键盘、晃鼠标感觉不卡）。

⚠️ 调度的核心矛盾：鱼和熊掌不可兼得！ 追求极致的周转时间（全速把一批任务怼完），往往会严重牺牲响应时间（某些任务被晾很久）；反过来追求极致的快速响应，又会被上下文切换和切片轮转拖慢整体完成进度。

五、基本调度算法演进：打破假设的打怪之路

5.1 擂台一：FIFO（先来先服务）

• 规则：排队买票，谁先来谁先跑（First In, First Out）。

• 打破假设 1（若作业长短不一）：
  假设任务 A 跑 100 秒，紧随其后的任务 B 和 C 各自只需 1 秒。

• 甘特图（Gantt Chart）：

  先 A，再 B、C

  A

  0102

  任务 A任务 B任务 C

  区间：A 0—100；B 100—101；C 101—102。窄色块的标注列在这里，避免文字挤在一起。 横轴单位为秒，色块宽度与执行时间成正比；窄屏可横向滚动。

• 💥 翻车点：护航效应（Convoy Effect）
  一辆大货车（长任务 A）慢吞吞霸占了整条单行道，后面紧紧跟着两辆轻巧的小轿车（短任务 B、C），小轿车只用开 1 秒，却被迫在大货车屁股后面吸了 100 秒尾气！平均周转时间被无情拖垮。

5.2 擂台二：SJF（最短作业优先）

• 规则：为了解决护航效应，谁耗时短谁先跑（Shortest Job First）！

• 甘特图（全员同时到达时刻 0 时）：

  全部在时刻 0 到达

  A

  0102

  任务 A任务 B任务 C

  区间：B 0—1；C 1—2；A 2—102。 横轴单位为秒，色块宽度与执行时间成正比；窄屏可横向滚动。

  短任务 B 和 C 瞬间完成，平均周转时间直接从天花板掉到地板，最优解诞生！

• 打破假设 2（若作业不是同时到达）：
  如果任务 A 在时刻 0 到达并占住了 CPU；任务 B 和 C 在时刻 1 到达。

• 💥 翻车点：迟到的短作业只能干等
  因为 SJF 是非抢占式的，即便 B 和 C 耗时再短，只要 A 已经上车，CPU 就不能踩刹车，B 和 C 依然要等待 99 秒。

5.3 擂台三：STCF（最短剩余时间优先，抢占式 SJF）

• 规则：打破假设 3（允许抢占 Preemptive）！

• 只要有新任务进入就绪队列，系统立即对比：当前新任务的耗时，是否短于正在跑的任务剩余未跑的耗时？

  • 若是，强行踩刹车剥夺当前任务的 CPU，改跑耗时更短的新任务（抢占）！

• 甘特图：

  B、C 在时刻 1 到达；同长时先 B

  A

  0102

  任务 A任务 B任务 C

  区间：A 0—1；B 1—2；C 2—3；A 3—102。 横轴单位为秒，色块宽度与执行时间成正比；窄屏可横向滚动。

• 优势：在全场景下保证了极其优秀的平均周转时间！

• 💥 翻车点：响应时间惨败（长任务面临无限饥饿）
  如果系统中源源不断有小任务（B、C、D、E...）涌入，大任务 A 的剩余时间永远是最长的，它将被无限期挂起（Starvation / 饥饿）。如果是交互式图形程序，用户界面将彻底冻结！

5.4 擂台四：RR（Round Robin 时间片轮转）

• 规则：为了拯救交互响应时间，彻底打破“一次跑完”的做法！

• 每个进程每次只允许运行一个时间片（Time Slice / Quantum），用完立即由时钟中断打断，排到队列尾部，轮到下一个人。

• 甘特图对比（时间片 = 1s）：

  示例：每个任务各需 5 秒，Q = 1 秒

  ABCABCABCABCABC

  015

  任务 A任务 B任务 C

  完成时刻：A = 13；B = 14；C = 15。忽略切换开销。 横轴单位为秒，色块宽度与执行时间成正比；窄屏可横向滚动。

• 神级表现：首次响应时间极佳！所有任务都能在极短时间内“摸到 CPU”，人机交互丝滑无比。

• 💥 翻车点：周转时间反向恶化
  如果三个任务都跑 5 秒，在 SJF 下前两个能很早完成；在 RR 下，所有任务被切碎同步推进，大家一起熬到第 13、14、15 秒才彻底完成。

5.5 三大经典策略横向数据对比

假设 A、B、C 都在时刻 0 到达，耗时分别为 8、4、1，就绪顺序 A→B→C：

5.6 现实的最后一击：引入 I/O 与“没有预言家”

现实系统逼着我们打破最后两个最致命的假设：

1. 打破假设 4：结合 I/O 实现重叠（Overlap）

进程不会一直死算，它会读写磁盘。当进程 A 发起 I/O 进入阻塞状态（Blocked）时，CPU 绝不闲着，调度器立即切走给进程 B 跑。这样 I/O 传输与 CPU 计算并行重叠，硬件利用率拉满！

2. 打破假设 5：没有上帝视角（No More Oracle）

SJF 和 STCF 算得再好，前提都是假设 5 成立——“事先知道任务要跑多久”。
但现实中，用户点开一个浏览器、跑一段 Python 脚本，操作系统根本无法预卜先知它究竟要跑 5 毫秒还是 5 小时！

🔮 悬念与终极救星：如果无法知道任务的长短，我们怎样才能既拥有 SJF 的极致周转率，又拥有 RR 的神速响应呢？
👉 这便催生了下一章的终极大招：MLFQ（多级反馈队列）——“既然无法预知未来，那就用你的历史行为预测未来！”

六、MLFQ：不知道任务长度怎么办

多级反馈队列（Multi-Level Feedback Queue, MLFQ） 由图灵奖得主 Fernando Corbato 于 1962 年提出。它的终极目标是：在操作系统没有任何“先验知识”（完全不知道任务究竟要跑 5 毫秒还是 5 小时）的前提下，既能像 SJF/STCF 一样拥有极短的周转时间，又能像 RR 一样保证交互任务的神速响应。

它的核心设计哲学是：“用过去的历史行为，预测未来的需求”。

6.1 MLFQ 的 5 大黄金调度规则 ⭐

《操作系统导论》（OSTEP 第 8 章）将演进完善后的 MLFQ 归纳为 5 条经典规则：

6.2 规则背后的攻防博弈：为什么必须是这 5 条规则？

理解 MLFQ 不能仅停留在死记 5 条规则，关键在于理解规则 4 和规则 5 解决的两次重大架构危机。

1. 规则 4 的演进：如何击溃“愚弄调度程序（Gaming the Scheduler）”？

在初代设计中，优先级的降级逻辑曾被写为两条看似合理的简单规则（规则 4a 与 4b）：

• 规则 4a：若工作用完一整个时间片，说明它是长计算，降低一级优先级；
• 规则 4b：若工作在时间片用完之前主动释放 CPU（比如发起了 I/O），则保持其当前优先级不变。

设计者的初衷是保护交互型任务（因为交互任务经常需要等待键盘输入或磁盘读取）。
然而，这留下了极其致命的安全漏洞——调度作弊！

😈 黑客作弊场景：
假设顶级队列 Q2 的时间片为 10ms。一个 CPU 密集型的长计算进程，只需在运行到 9.9ms 时，故意发起一次无关紧要的微小 I/O 操作（例如向空设备写一个字节或读一个无用扇区）主动放弃 CPU。
按照旧规则 4b，调度器认为它“没有用完时间片就主动让出”，因此它的优先级永远不会下降！
于是该恶意进程可以反复循环：占用 9.9ms -> 主动放弃 -> 立即回到就绪队尾 -> 再次占用 9.9ms，在 99% 的物理时间里永久霸占 CPU，将其他正常进程彻底排挤饿死！

终极防御（优化后的规则 4）：
调度器引入配额累计记账（Time Allotment）：

• 调度器为每个进程在每一层级记录其实际消耗的 CPU 物理运行时间总和；
• 不论进程在时间片结束前主动让出了多少次 CPU，该计数器只做增量累加；
• 只要在本层的累计运行时间达到了该层的配额（如 10ms），强制降级！ 彻底堵死了调度作弊的漏洞。

2. 规则 5 的诞生：解决“饥饿”与“行为突变”

即便有了规则 1 到 4，系统仍面临两大致命缺陷：

1. 饥饿问题（Starvation）：如果系统中源源不断有新的短任务或交互任务（如用户连续快速敲击键盘、浏览器不断加载小资源）进入系统，高优先级队列 Q2 永远不空。根据规则 1，沉底在 Q0 的 CPU 密集型任务将永远得不到任何 CPU 时间，活活饿死！
2. 行为突变（Change of Behavior）：一个原本在后台进行长时间复杂矩阵运算的进程，在算完数据后需要弹窗等待用户交互。但此时它已经被规则 4 压在了最底层的 Q0 队列，导致后续的按键交互极度卡顿，无法恢复响应性。

终极解决方案（规则 5 周期性提升 Priority Boost）：
引入系统级全局时间周期 $S$：每隔时间 $S$，调度程序将系统中所有进程全部重新扔回最高优先级 Q2 队列！

• 底层进程永不饿死：被提升回 Q2 后，即便高层任务再多，根据规则 2，它也能通过轮转（RR）切分到 CPU 时间，确保进度持续推进；
• 行为突变进程瞬间“复活”：若它确实已转变为交互型任务，在被提升回 Q2 后，由于其后续只做少量短计算便主动等待 I/O，消耗的配额极少，能够自然留存在高优先级队列中。

6.3 工程调优：为什么不同队列的时间片长度不同？

现实操作系统（如 Solaris、FreeBSD 的调度器）在实现 MLFQ 时，通常采用变长时间片策略：

• 高优先级队列（Q2）：时间片极短（如 10ms），确保鼠标移动、按键响应等极短事件毫秒级完成，换取极致的交互响应；
• 低优先级队列（Q0）：时间片成倍拉长（如 100ms 甚至数百毫秒），因为底层全部是长计算任务，拉长时间片能让进程充分利用 CPU 缓存，并大幅减少上下文切换的开销，从而最大化整机计算吞吐率。

七、比例份额调度与多处理器

前面介绍的 FIFO、SJF、RR 以及 MLFQ，核心优化目标都是传统的性能指标：要么追求极致的周转时间（Turnaround Time），要么追求极致的响应时间（Response Time）。

而另一类完全不同的调度哲学被称为 比例份额（Proportional Share）调度，有时也称 公平份额（Fair Share）调度。

🎯 核心目标：调度器的终极使命不是优化快慢，而是确保每个进程获得严格按比例划分的 CPU 物理时间份额。例如：系统有 2 个进程，A 应当获得 75% 的 CPU 时间，B 应当获得 25% 的 CPU 时间。

7.1 彩票调度（Lottery Scheduling）：用随机性化解复杂性 ⭐

1994 年由 Carl Waldspurger 和 William Weihl 提出的 彩票调度（Lottery Scheduling） 是比例份额调度中最精彩的现代经典。

1. 核心概念：彩票数表示份额

• 彩票（Ticket） 代表了进程占有 CPU 资源的份额比例。
• 一个进程拥有的彩票数占全系统总彩票数的百分比，就是它在统计上占有 CPU 运行时间的比例。
• 调度过程：每隔一个时间片，调度器举办一次“彩票抽奖”：在全局总彩票数（如 0 到 $\text{total\_tickets} - 1$）中生成一个随机中奖号码。哪一个进程持有该号码，哪一个进程就中奖并获得该时间片的 CPU 执行权！

💡 为什么随机性（Randomness）如此强大？

1. 避免边界死锁与病态对抗：传统的确定性算法常在特定边角模式下崩溃（如 LRU 遇上循环遍历直接命中率归零）；而随机算法不会存在最差对抗输入，行为极具鲁棒性；
2. 轻量且无全局历史状态：调度器不需要追踪每个进程过去究竟跑了多少毫秒、不需要维护复杂的衰减平均值，抽奖只看眼前；
3. 极速动态伸缩：新进程加入或旧进程退出，只需对全局彩票总数做简单加减即可，无需任何重平衡计算。

2. 底层链表实现与降序遍历优化

操作系统如何在微秒级内从链表中定位中奖者？

// 经典彩票遍历算法
int counter = 0;
// 从 [0, total_tickets - 1] 抽取一个中奖号码
int winner = get_random(0, total_tickets);

node_t *current = head;
// 遍历链表，累加彩票，直到累加和严格大于中奖号码
while (current) {
    counter += current->tickets;
    if (counter > winner) {
        break; // 找到了中奖者！
    }
    current = current->next;
}
// 调度 current 进程运行...

⚡ 性能优化技巧（链表按彩票数递减排序）：
现实系统中，大多数彩票往往集中在少数高优先级或高份额进程手中。如果将就绪进程链表按其彩票数从大到小降序排列，遍历时 counter 会以极快的速度越过 winner，平均只需 1~2 次指针跳跃即可锁定中奖者，大幅提升调度循环的执行效率！

3. 三大灵活的彩票机制（Ticket Mechanisms）

彩票调度之所以富有工程魅力，在于它支持三种高度灵活的操作机制：

4. 随机性的代价：不公平度指标（Unfairness Metric, $U$）

假设有两个各持 100 张彩票（各占 50% 份额）、且运行时间同为 $R$ 的任务 A 和 B。我们期望它们在大约同一时刻完成。
为了量化衡量调度的不公平性，定义指标 $U$：
$U = \frac{\text{先完成工作的结束时间}}{\text{后完成工作的结束时间}}$

• 完美公平：两任务同时结束，此时 $U = 1$；
• 极端不公平：A 跑完全程 B 才开始，若 $R=10$，A 在 10 结束，B 在 20 结束，$U = 10 / 20 = 0.5$。

📊 大数定律的约束：

• 当任务运行时间很短（$R$ 仅有几个时间片）时，随机波动占据主导，硬币可能连续掷出正面，$U$ 的平均值极其糟糕（远小于 1）；
• 只有当任务运行时间非常长（经历数千个时间片）时，大数定律生效，各进程实际获得的 CPU 时间才会无限逼近理论份额比例（$U \to 1$）。

7.2 确定性比例调度：步长调度（Stride Scheduling）

为了解决彩票调度在短时间内的随机不公平问题，Waldspurger 提出了确定性算法——步长调度（Stride Scheduling）。

1. 核心数学模型

1. 步长（Stride）：每个进程的步长与它所拥有的彩票数成严格反比。
   选定一个足够大的系统整数常数 $L$（如 10000），计算：
   $\text{步长 } S_i = \frac{L}{\text{Tickets}_i}$
   含义：票数越多的进程，步长越小，走得越慢；票数越少的进程，步长越大，走得越快。
2. 行程值（Pass）：每个进程维护一个 pass 计数器，记录其历史累计行进距离（初始为 0）。
3. 调度黄金规则：

   每次选择当前 pass 值最小的进程运行！运行一个时间片后，将其 pass += stride，重新放回队列。

2. 手算实例推导追踪

设系统中有 A（100 票）、B（50 票）、C（250 票）三个进程，选取常数 $L = 10000$。

• $\text{Stride}(A) = 10000 / 100 = 100$
• $\text{Stride}(B) = 10000 / 50 = 200$
• $\text{Stride}(C) = 10000 / 250 = 40$

🎯 精妙的比例兑现：
在这 8 轮调度中：

• C 运行了 5 次；
• A 运行了 2 次；
• B 运行了 1 次。
  运行次数比例精确为 $5 : 2 : 1$，与票数 $250 : 100 : 50$ 完全绝对一致！ 步长调度在任何周期节点上都保持了确定性的严格公平。

7.3 彩票调度 vs 步长调度：既然步长绝对公平，为何还需要彩票？

很多初学者自然会问：步长调度算得这么准，彩票调度凭什么还有立足之地？
答案在于面对动态变化的现实系统时，两者的架构复杂度截然不同：

为什么比例份额没有成为通用操作系统的默认选择？

尽管彩票与步长调度设计极为巧妙，但现代通用操作系统（如 Linux 的 CFS 调度器、Windows、macOS）依然主要基于 MLFQ 及其变体，比例份额未能一统天下的根本原因在于：

1. 票数分配难题（The Ticket Allocation Problem）：系统怎么知道该给浏览器分配 300 张票，还是给编译脚本分配 100 张票？普通用户和管理员根本无法量化输入；
2. 难以适配 I/O 交互与睡眠模式：如果一个高票数进程长期休眠等待网络包，醒来后是否应该一次性“补偿”运行？补偿过多会引发抖动，不补偿又丢失了比例承诺；
3. 最佳落地领域：虚拟化与云计算（如 VMware ESX Hypervisor）。在虚拟机管理中，租户购买了 4 核或 20% 的算力配额，各 VM 边界清晰、比例明确，比例份额调度在这类场景下得到了淋漓尽致的发挥。

7.4 多处理器调度：缓存亲和性 vs 负载均衡

现代多核系统中，调度器需权衡 缓存亲和性（Cache Affinity） 与 负载均衡（Load Balancing）：

• 单队列调度（SQMS）：所有核共享一个全局就绪队列。负载天然均衡，但核间对全局队列锁争用严重，且任务在不同核之间漂移会导致 CPU 缓存命中率严重下降。
• 多队列调度（MQMS）：每个核心维护独立的专属就绪队列。各核无锁争用，任务固定在同一核上执行故缓存利用率极高；但容易出现某些核空闲而某些核过载的负载不均现象。
• 工作窃取（Work Stealing）：MQMS 的通用解决方案——空闲核心主动从负载过高的其他核队列尾部“窃取”任务执行，兼顾了局部缓存亲和与全局负载均衡。

八、自测与核心记忆点

1. ⭐ 启动程序成为进程需要哪些步骤？
   • 建记录 → 建空间 → 备环境 → 设上下文 → 等调度。分配 PCB、建立虚拟地址空间、初始化栈空间与参数、设定 PC/SP 等初始上下文，放入就绪队列等待调度器选中。
2. ⭐ I/O 完成后，状态为什么是“阻塞 → 就绪”而不是直接“阻塞 → 运行”？
   • I/O 完成仅代表任务重新具备了运行条件，必须重新进入就绪队列接受调度器的裁决与 CPU 分配，逻辑上不能直接抢占正在运行的进程。
3. ⭐ fork() 后子进程从哪里开始执行？为什么不从 main() 开始？
   • 从 fork() 返回点继续向下执行。因为子进程复制了父进程当时的执行上下文（包括程序计数器 PC）；内核通过返回值区分身份（子进程返回 0，父进程返回子 PID）。
4. Unix 为什么把进程创建拆分为 fork() 与 exec() 两部分？
   • 为子进程在创建后、运行新程序前留出了环境配置的操作窗口（如重定向标准 I/O、建立管道），目标程序无需包含任何外部重定向代码。
5. 为什么子进程修改局部变量（如 x = 20）不会影响父进程？
   • 父子拥有各自独立的虚拟内存空间。物理上采用写时复制（COW）：未写入时共享只读页，一旦写入触发写保护异常，内核按需为修改方分配私有物理页。
6. 阻塞进程应不应该继续占用 CPU？为什么没有“就绪 → 阻塞”？
   • 不应占用，空等浪费算力；就绪任务未占用 CPU 执行指令，不可能自行发起阻塞操作。
7. ⭐ SJF 在现实通用系统中能否直接使用？MLFQ 的 5 个核心规则是什么？
   • 不能直接使用 SJF 的原因：操作系统没有预卜先知的“上帝视角”，无法预先获知任务未来的具体执行时长。
   • MLFQ 的 5 大黄金规则：
     1. Priority(A) > Priority(B)：运行 A，不运行 B（严格优先级抢占）；
     2. Priority(A) = Priority(B)：轮转（Round-Robin）运行 A 和 B；
     3. 新任务进入系统：默认放入最高优先级队列（乐观假设为短任务，逼近 SJF）；
     4. 用完本层时间配额（无论中间主动放弃了多少次 CPU）：降低其优先级（配额累计记账，击溃“在时间片末尾主动做微小 I/O”的调度作弊）；
     5. 每隔时间周期 $S$：将系统中所有存活任务重新拉回最高优先级队列（Priority Boost，彻底解决底层饥饿与行为突变）。
8. exec() 是否创建了新进程？僵尸进程与孤儿进程的区别是什么？
   • exec() 不创建新进程，只是替换当前进程的程序映像，PID 保持不变；
   • 僵尸进程：已终止但退出状态尚未被父进程 wait() 回收，内核仍保留其 PCB 记录；
   • 孤儿进程：原父进程先退出，存活的子进程被系统祖先（如 init / systemd）接管关系。
9. 什么叫做受限直接执行（Limited Direct Execution, LDE）？
   • “直接执行”让非特权指令直接在物理硬件上运行以追求原生性能；“受限”通过特权级分离（用户态/内核态）限制硬件访问，并通过硬件时钟中断防止死循环霸占 CPU，从而在高性能与强控制之间取得平衡。
10. 用户态与内核态的核心区别是什么？为什么发生系统调用进入内核时必须切换到内核栈？
    • 区别：硬件模式位赋予的权限不同。用户态仅能执行非特权指令且内存访问受限；内核态拥有对所有硬件外设与特权指令的最高控制权。
    • 切换内核栈的原因：
      1. 安全性：用户栈位于用户空间可被指针任意篡改，内核栈受保护，防止恶意代码劫持特权执行流；
      2. 健壮性：用户栈可能已溢出或指针非法，使用独立的内核栈可避免内核压栈时引发连续硬件故障导致整机崩溃。
11. 中断向量表（IVT）与上下文保存是什么关系？两层上下文分别保存在哪里？
    • 关系：中断向量表负责“寻址路由”（依据中断/陷阱向量号告诉 CPU 该跳往哪个内核处理入口），上下文压栈负责“保护现场”（在打断当前指令流前将寄存器快照保存下来，以便后续恢复）；两者在硬件进入内核态时紧密咬合。
    • 保存位置：
      1. 用户态上下文（Trap Frame / 陷阱帧）：保存在当前进程的内核栈顶端（硬件自动压入 PC/SP/Flags + 汇编压入通用寄存器）；
      2. 内核态调度上下文：保存在进程的 PCB（或 thread_struct） 中（由调度器 switch_to 在进程切换轮转时保存与恢复）。
12. 上下文切换最昂贵的开销是什么？它如何决定了调度时间片（Time Slice）的设计？
    • 最昂贵开销：并非保存/恢复寄存器的微秒级直接开销，而是缓存污染（Cache Thrashing / Cold Cache）。新进程会冲刷掉 CPU 的 L1/L2 缓存与 TLB 快表，切回原进程时面临严重 Cache Miss，访存延迟暴增上百倍。
    • 对时间片的设计约束：
      • 时间片太短（如 1ms）：切换开销与缓存损耗占比过高（$>10\%$），CPU 尽在打白工，系统吞吐量雪崩；
      • 时间片太长（如 1000ms）：交互响应极差，用户感到明显卡顿；
      • 黄金折中：现代通用 OS 将时间片通常设为 10ms～50ms，使切换开销占比 $<1\%$，同时兼顾丝滑交互。

教材主题可从 OSTEP 作者目录查阅第 4—10 章；API 的具体语义可结合本篇链接的系统手册核对。